package levelorder;

import entity.TreeNode;

import java.util.*;

public class LevelOrderTraversal {
    /*
    * 二叉树的层序遍历
    * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。
    * （即逐层地，从左到右访问所有节点）。
    *
    * 树中节点数目在范围 [0, 2000] 内
    * -1000 <= Node.val <= 1000
    *
    * 队列先进先出，符合一层一层遍历的逻辑
    * */
    public static void main(String[] args){
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        LevelOrderTraversal o = new LevelOrderTraversal();
        o.mySolution(root);
    }

    // 迭代方式，借助队列，队列先进先出，符合一层一层遍历的逻辑
    public List<ArrayList<Integer>> mySolution(TreeNode root){
        List<ArrayList<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()){
            ArrayList<Integer> r = new ArrayList<>();
            int len = deque.size();
            while (len > 0){
                root = deque.pop();
                r.add(root.val);
                if(root.left != null) deque.add(root.left);
                if(root.right != null) deque.add(root.right);
                len--;
            }
            res.add(r); // 写入结果
        }
        return res;
    }

    // 递归方式
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> solution(TreeNode root){
        if(root == null)
            return res;
        traversal(root, 0);
        return res;
    }

    private void traversal(TreeNode node, int deep){
        if(node == null) return;    // 返回条件，这层为空

        deep++; // deep从0开始，每调用一层便加1
        if(res.size() < deep){
            // 层级比结果集大，要添加新的结果集
            ArrayList<Integer> r = new ArrayList<>();
            res.add(r);
        }
        // 将该层结果加入结果集，用deep来锁定该层所在的结果集索引
        res.get(deep-1).add(node.val);
        // 左右深入
        traversal(node.left, deep);
        traversal(node.right, deep);
    }
}

